class Solution(object):
    def numDupDigitsAtMostN(self, n):
        n = str(n)
        m = len(str(n))
        def judge(i, mask, dump, restrict):
            if i == m:
                if dump:
                    return 1
                else:
                    return 0
            upper =  int(n[i]) if restrict else 9
            ans = 0
            for j in range(upper + 1):
                if not mask:
                    if j == 0:
                        ans += judge(i + 1, 0, False, False)
                    else:
                        ans += judge(i + 1, 1 << j, False, restrict & (j == upper))
                else:
                    ans += judge(i + 1, mask | (1 << j), dump | ((mask & (1 << j)) > 0)  , restrict & (j == upper))
            return ans
        return judge(0, 0, False, True)



data = Solution()
n = 1000
print(data.numDupDigitsAtMostN(n))